#include <iostream>
#include <algorithm>
#include<queue>
#include<cstring>
#define IOS ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const int N=5e2+10;
int n;
int mp[N][N],h[N],l[N];
bool st[N];
void solve(){
	cin>>n;
	for(int i=1;i<=n;i++) h[i]=l[i]=0x3f3f3f3f;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
			cin>>mp[i][j];
			h[i]=min(h[i],mp[i][j]);
			l[j]=min(l[j],mp[i][j]);	
		} 
	}
	ll H=0,L=0;
	memset(st,0,sizeof st);
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
			if(mp[i][j]==h[i]&&!st[i]){
				st[i]=1;
				H+=mp[i][j];
//				cout<<'H'<<mp[i][j]<<endl;
			}else if(mp[i][j]<0) H+=mp[i][j];	
		} 
	}
	memset(st,0,sizeof st);
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
			if(mp[i][j]==l[j]&&!st[j]){
				st[j]=1;
				L+=mp[i][j];
//				cout<<'L'<<mp[i][j]<<endl;
			}else if(mp[i][j]<0) L+=mp[i][j];	
		} 
	}
	cout<<min(H,L)<<'\n';
}

int main()
{
	IOS;
	int t=1;
	cin>>t;
	while(t--) solve();
	return 0;
}
/*
1
4
-8 -8 2 9
-7 -8 8 3
-8 -1 4 3
-3 -2 8 7
*/
